package bit2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size=0;
        head=new ListNode(0);
    }

    public int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        ListNode cur=head;
        for(int i=0;i<=index;i++){
            cur=cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0,val);
    }

    public void addAtTail(int val) {
        addAtIndex(size,val);
    }

    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if (index <=0) index = 0;
        ++size;
        ListNode pre = head;
        for(int i = 0; i < index; ++i) {
            pre = pre.next;
        }
        ListNode node = new ListNode(val);
        node.next = pre.next;
        pre.next = node;
    }

    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        size--;
        ListNode cur=head;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.next=cur.next.next;

    }
}
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}
public class Main {
    public static void main4(String[] args) {
       int grid[][]={{3,8,1,9},{19,7,2,5},{4,6,11,10},{12,0,21,13}};
       int arr[]=new int[grid.length*grid[0].length];
       int count=0,sum=arr.length;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                arr[count++]=grid[i][j];
            }
        }
        int k=4;
        for (int i = 0; i < k; i++) {
            int tmp=arr[sum-1];
            for (int j = sum-1; j>0; j--) {
                arr[j]=arr[j-1];
            }
            arr[0]=tmp;
        }
        count=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                grid[i][j]=arr[count++];
            }
        }
        List<List<Integer>> lists = new ArrayList<>(grid.length);
        for (int i = 0; i < grid.length; i++) {
            List<Integer> temp=new ArrayList<>();
            for (int j = 0; j < grid[i].length; j++) {
                temp.add(grid[i][j]);
            }
            lists.add(temp);
        }
    }
    public static int getImportance(List<Employee> employees, int id) {
        for(Employee e:employees){
            if(id==e.id){
                if(e.subordinates.size()==0){
                    return e.importance;
                }
                for(int n1:e.subordinates){
                    e.importance+=getImportance(employees,n1);
                }
                return e.importance;
            }
        }
        return 0;
    }
    public static int findJudge(int n, int[][] trust) {
        int arr[]=new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < trust.length; j++) {
                if(i+1==trust[j][1]&&trust[j][0]!=i+1){
                    arr[i]++;
                }
                if(i+1==trust[j][0]){
                    arr[i]--;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==n-1){
                return i+1;
            }
        }
        return -1;
    }
    public static void main3(String[] args) {
        int trust[][]={{1,3},{2,3},{3,1}};
        int n=3;
        System.out.println(findJudge(n,trust));
    }
    public static List<List<Integer>> shiftGrid(int[][] grid, int k){
        return new LinkedList<>();
    }
    public static void main2(String[] args) {
        int [][]grid={{1,2,3},{4,5,6},{7,8,9}};
        List one=shiftGrid(grid,1);

    }
    public static boolean canThreePartsEqualSum(int[] arr) {
        int n= arr.length,sum=0,i=0,sum1=0;
        for (int num:arr) {
            sum+=num;
        }
        if(sum%3!=0){
            return false;
        }
        int target=sum/3;
        while (i<n){
            sum1+=arr[i];
            i++;
            if(sum1==target){
                break;
            }
        }
        if (sum1!=target){
            return false;
        }
        while (i+1<n){
            sum1+=arr[i];
            i++;
            if(sum1==target*2){
                return true;
            }
        }
        return false;
    }
    public static void main1(String[] args) {
        int arr[]={1,-1,1,-1};
        System.out.println(canThreePartsEqualSum(arr));
    }
}
